Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Networks and Graph Theory - Finding the shortest path.
Test Yourself 1 - Solutions.


 

1. Find the shortest path from A to F.

 

A(0)

B(2)

D(3)

E(4)

 B

2

 

 

 

 C

 

 

 

7

 D

4

3

 E

 

4

6

 F

 

 

 

6

    

Step 1: AB is shorter than AD.

Step 2: BD = 3 (from A) is shorter.

Step 3: DE (remember this is really ABDE) = 6
but the path above (ABE) = 4 and is therefore shorter - so cancel D.

Step 4: E could go to B - but that vertex has already been visited - so options are C or F. F is shorter and is our target.

Shortest path is therefore A, B, E and F with a length of 6.

                
2. Find the shortest path from A to G.

 

A(0)

B(6)

D(11)

C(12)

E(17)

 B

6

 C

 

12

15

 D

 

11

 E

 

 

22

17

 F

 

 

23

 G

 

 

 

 

23

  

Step 1: B is shortest (and only!)

Step 2: BD is shorter.

Step 3: DC is shorter (=15) but ABC = 12 is a shorter path to C.

Step 4: CE is really the only path as D has been visited and rejected.

Step 5: EG is the only path remaining giving the shortest path as A, C, E and G with a total weight of 23.

                
3. Find the shortest path from A to C.
  

A(0)

B(5)

H(7)

F(9)

G(10)

E(15)

D(10)

 B

5

 

15

 C

 

16

 

 

 

18

14

 D

 

10

 

 

 

22

 E

 

 

 

19

15

 F

 

9

 

 

 

25

 G

 

11

17

10

 H

7

13
Step 1: AB is shortest.

Step 2: the 13 for H is ignored so consider 7.

AH is shortest at 7.

Step 3: HB is shorter than HG but B from A is 5 so eliminate H leaving ABF as the shortest = 9.

Step 4: FG = 10 is the shortest and also replaces those links above.

Step 5: GE = 15 is shortest

Step 6: The 22 for D is replaced by BD = 10 above. That is now the shortest path to D.

Step 7: D only links to C giving the path A, B, D then C as the shortest with a total weight of 14.

                
4.
  B A C D E F G I H
B   12 15 19          
A (12)         18        
E (18)     16     20      
  NOTE: the 15 from B to C is smaller than the 16 from B-A-E-C so ignore path via E.  
C (15)           7 16    
F (7)             8   15
G (8)               17 6

∴shortest path from B to H is B-C-F-G-H with a path length of 15+7+8+6 = 36 hours.

5.

  M AG S G VP H
GH 5 7        
M (5)     3 6    
S (3)       2 3  
G (2)           4

The minimum path is therefore:

The minimum cost is $14.

7.

  A B C D E F G H I J
A   1 8 4         1  
AB (1)     8   6          
ABE (12)     3              
ACE (8) 8     2            
AD (4)           9       1
ADJ(5)           3   6    
ADJF (8)               2    

So the minimum path is A-D-J-F-H and it is of length 10.